package com.ken.algorithms.stack;

import java.util.Stack;

/**
 * <ul>
 * <li>Title: MainCD16</li>
 * <li>Description: TODO </li>
 * </ul>
 *
 * @author 程序员ken
 * @date 2021/5/19 0019 上午 11:32
 */
public class MainCD16 {

    public static void main(String[] args) {
        int[] [] area ={{1,1,1,0,1},{1,1,1,1,1},{0,1,1,0,1},{0,1,1,1,1}};;
        System.out.println(maximalRectangle(area));

    }

    private static int maximalRectangle(int[][] area) {

        if(area==null || area[0]==null || area[0].length<=0){
            return 0;
        }
        int maxArea = 0; // 最大矩形面积
        //Long res =0L;
        int[] height = new int[area[0].length]; // 分别以每行作为底，每个位置往上的 1 的数量

        for (int i = 0; i <area.length ; i++) {
            for (int j=0;j<area[0].length;j++){
                height[j] = area[i][j] == 0?0:height[j]+1;// 宽度和高度 弄混了  单个数组长度即为高的个数
            }
            //没有对比每行的高度 最大
            maxArea = Math.max(maxArea, maxRecFromBottom(height));
        }

        return maxArea;
    }


    // 计算柱状图中（height数组）最大的矩形
    private static int maxRecFromBottom(int[] heights) {
        //左右边界加入‘0’
        int[] newHeights = new int[heights.length+2];
        newHeights[0] =0;
        newHeights[heights.length+1] =0;

        for (int i = 0; i < heights.length; i++) {
            newHeights[i+1] = heights[i];
        }

        // 定义最终结果初始值为0
        Stack<Integer> stack = new Stack<Integer>();
        int res =0;

        for (int i = 0; i < newHeights.length; i++) {
            // 如果栈不为空并且当前遍历到的矩形高度小于栈顶矩形的高度，
            // 则表示以当前栈顶矩形为高的矩形面积可以确定
            while (!stack.isEmpty() && newHeights[stack.peek()]> newHeights[i]){
                int cur = stack.pop();
                int curMaxHeight =  newHeights[cur];//获取当前最高的高度
                int leftSide = stack.peek();//左侧 cur-1;//
                int rightSide =i;
                int curWidth  = rightSide-leftSide-1;//间隔数
                res = Math.max(res,curMaxHeight*curWidth);
            }
            stack.push(i);//加入高度的索引
        }
        return res;
    }


}
